import java.util.Iterator;

public class LinkList<T> implements Iterable<T> {
    // 头节点
    private Node<T> head;
    // 尾节点
    private Node<T> tail;
    // 节点个数
    private int size;

    public LinkList() {
        head = new Node<T>(null, null, null);
        tail = new Node<T>(null, head, null);
        head.next = tail;
        size = 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkListIterator();
    }

    /**
     * 链表节点定义
     *
     * @param <T> 数据类型
     */
    private static class Node<T> {
        T item;
        Node<T> prev;
        Node<T> next;

        Node(T item, Node<T> prev, Node<T> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    /**
     * 获取节点个数
     *
     * @return 节点个数
     */
    public int size() {
        return size;
    }

    /**
     * 判断链表是否为空
     *
     * @return 布尔值
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 获取指定位置的Node节点
     *
     * @param index 索引值
     * @return Node
     */
    private Node<T> getNode(int index) {
        Node<T> node;
        // 索引值错误时抛出异常
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        // 如果索引位置小于一半的长度就从头节点开始找，否则从尾节点开始
        if (index < size() / 2) {
            node = head.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = tail;
            for (int i = 0; i < index; i++) {
                node = node.prev;
            }
        }
        return node;
    }

    /**
     * 指定位置插入
     *
     * @param index 索引值
     * @param item  待插入数据
     */
    public void insert(int index, T item) {
        var node = getNode(index);
        var newNode = new Node<T>(item, node.prev, node);
        newNode.prev.next = newNode;
        node.prev = newNode;
        size++;
    }

    /**
     * 在链表结尾添加数据
     *
     * @param item 待添加数据
     */
    public void add(T item) {
        insert(size(), item);
    }

    /**
     * 删除指定节点
     *
     * @param node 节点
     * @return 被删除数据
     */
    private T remove(Node<T> node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        size--;
        return node.item;
    }

    /**
     * 根据索引位置删除
     *
     * @param index 索引值
     * @return 被删除数据
     */
    public T remove(int index) {
        return remove(getNode(index));
    }

    /**
     * 删除最后一个数据
     *
     * @return 删除数据
     */
    public T remove() {
        return remove(size() - 1);
    }

    /**
     * LinkList迭代器
     */
    private class LinkListIterator implements Iterator<T> {
        private Node<T> current = head.next;

        /**
         * 判断迭代器是否有下一个数据
         *
         * @return 布尔值
         */
        @Override
        public boolean hasNext() {
            return current != tail;
        }

        /**
         * 获取当前迭代数据，并推进迭代器
         *
         * @return 当前迭代数据
         */
        @Override
        public T next() {
            var item = current.item;
            current = current.next;
            return item;
        }

        /**
         * 删除节点
         */
        @Override
        public void remove() {
            LinkList.this.remove(current.prev);
        }
    }
}